public class MaxPQ
        <Key extends Comparable<Key>> {
    /*<Key extends Comparable<Key>>是Java的泛型语法。
    它指示了MaxPQ类使用一个类型参数Key，并且要求这个类型Key必须实现了Comparable<Key>接口。
    Comparable<Key>接口是Java中定义的一个泛型接口，用于比较两个对象的顺序。
    它要求实现类具有比较自身与其他对象的能力，并返回一个整数值表示它们的相对顺序。
    通过实现Comparable接口，我们可以在堆和优先级队列中比较元素的大小，以维护它们的排序规则。
    在这段代码中，Key作为泛型参数限制了存储在pq数组中的元素类型必须实现Comparable接口，以便能够进行比较操作（例如使用compareTo方法）。
    这样做可以确保我们能够正确地进行插入、删除和获取最大元素等操作，使得堆和优先级队列能够按照特定的顺序进行排序和处理。*/
    /*完全二叉树中的索引下标是可以计算出来的*/
    // 父节点的索引
    int parent(int root) {
        return root / 2;
    }
    // 左孩子的索引
    int left(int root) {
        return root * 2;
    }
    // 右孩子的索引
    int right(int root) {
        return root * 2 + 1;
    }

    // 存储元素的数组
    private Key[] pq;
    // 当前 Priority Queue 中的元素个数
    private int size = 0;

    public MaxPQ(int cap) {
        // 索引 0 不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
        /*在这段代码中，pq = (Key[]) new Comparable[cap + 1];是用来创建一个泛型数组的操作。
        首先，我们需要了解在Java中创建泛型数组的限制。由于Java的类型擦除机制，无法直接创建一个具体类型的泛型数组。
        因此，我们只能通过创建一个非泛型数组，然后将其转换为泛型数组。
        在这段代码中，new Comparable[cap + 1]创建了一个长度为cap + 1的非泛型数组，
        并且元素的类型是Comparable接口。这个数组在内存中被分配了空间。
        然后，(Key[])表示进行了一个类型转换。
        因为我们知道该数组是要存储Key类型的元素，所以我们将其强制转换为泛型数组类型Key[]。
        最后，将转换后的泛型数组赋值给变量pq，使得pq引用这个泛型数组。
        需要注意的是，在进行强制类型转换时，存在一定的风险。
        如果实际存储在数组中的元素类型不符合泛型参数Key的约束条件，可能会导致运行时错误。
        因此，在使用该代码时，应确保泛型参数和实际存储的元素类型是匹配的。*/
    }

    /* 返回当前队列中最大元素 */
    public Key max() {
        return pq[1];
    }

    /* 插入元素 e */
    public void insert(Key e) {
        size++;
        // 先把新元素加到最后
        pq[size] = e;
        // 然后让它上浮到正确的位置
        swim(size);
    }

    /* 删除并返回当前队列中最大元素 */
    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];
        // 把这个最大元素换到最后，删除之
        swap(1, size);
        pq[size] = null;
        size--;
        // 让 pq[1] 下沉到正确位置
        sink(1);
        return max;
    }

    /* 上浮第 x 个元素，以维护最大堆性质 */
    private void swim(int x) {
        // 如果浮到堆顶，就不能再上浮了
        //因为是从索引1开始的，所以索引1是堆顶
        //判断：当x不是堆顶且x的父结点小于x时
        while (x > 1 && less(parent(x), x)) {
            // 如果第 x 个元素比上层大
            // 交换数组下标元素
            swap(parent(x), x);
            x = parent(x);
        }
    }

    /* 下沉第 x 个元素，以维护最大堆性质 */
    private void sink(int x) {
        // 如果沉到堆底，就沉不下去了
        while (left(x) <= size) {
            // 先假设左边节点较大
            int max = left(x);
            // 如果右边节点存在，比一下大小
            if (right(x) <= size && less(max, right(x)))
                max = right(x);
            // 结点 x 比俩孩子都大，就不必下沉了
            if (less(max, x)) break;
            // 否则，不符合最大堆的结构，下沉 x 结点
            swap(x, max);
            x = max;
        }
    }

    /* 交换数组的两个元素 */
    private void swap(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /* pq[i] 是否比 pq[j] 小？ */
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
}
